package question05;

/**
 * @author yuan
 * @date 2021/12/14
 */

/**
 * 题目：
 *      获取字符串的最长回文字符串
 * 思路：
 *      1、将字符串的每个字符挨个遍历，求出每个字符的最大回文长度，
 *      并将最长的回文字符串输出
 *      2、以遍历的字符串字符为中心点向两边扩散，定义 start，end，
 *      作为前一个字符和下一个字符的索引，如果 array[start] == array[end]
 *      则说明是回文，start--，end++，如果不相等并比之前的回文字符串长度更
 *      大，则更新 maxLength
 *      3、一条回文字符串的长度有两种情况，一种是长度为奇数，一种是长度为偶数
 *      奇数长度的回文字符串的条件是，当前字符与下一个字符相等，所以字符向两
 *      边扩散时，要先进行判断，如果 array[position] == array[position + 1]，
 *      则存在奇数长度回文字符串小于偶数回文字符串的情况，所以都要进行计算取最
 *      大值，如果不存在与下一个字符相等的情况，则直接计算即可。在计算偶数长度
 *      回文字符串的过程中，因为是以 position 和 position + 1 为中心点，所以要
 *      先将 end++
 */
public class Solution {

    public static void main(String[] args) {
        // System.out.println(new Solution().longestPalindrome("babad"));
        // System.out.println(new Solution().longestPalindrome("cbbd"));
        // System.out.println(new Solution().longestPalindrome("a"));
        // System.out.println(new Solution().longestPalindrome("ac"));
    }

    /**
     * 获取字符串的最长回文字符串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        // 字符串长度为 1
        if (s.length() == 1) return s;
        // 将字符串转换为字节数组
        char[] array = s.toCharArray();
        // 最大回文长度
        int maxLength = 0;
        // 中轴索引
        int positionIndex = 0;
        // 回文起始索引
        int startIndex = 0;
        while (positionIndex < array.length) {
            int length = palindromeMaxLength(array, positionIndex);
            if (length > maxLength) {
                maxLength = length;
                if (maxLength % 2 != 0) startIndex = positionIndex - (maxLength - 1) / 2;
                else startIndex = positionIndex - (maxLength - 2) / 2;
            }
            positionIndex++;
        }
        return s.substring(startIndex, startIndex + maxLength);
    }

    /**
     * 返回数组下标对应元素为中点的最大回文长度
     * @param array
     * @param positionIndex
     * @return
     */
    public static int palindromeMaxLength(char[] array, int positionIndex) {

        // 数组长度为 1
        if (array.length == 1) return 1;
        // 最大奇数长度回文
        int oddMaxLength;
        // 最大偶数长度回文
        int evenMaxLength = 0;
        // 获取最大奇数长度回文
        oddMaxLength = oddPalindromeMaxLength(array, positionIndex);
        // 只有当本元素与下一个元素相同时，才可能出现偶数长度回文字符串
        if (positionIndex + 1 < array.length && array[positionIndex] == array[positionIndex + 1]) {
            // 获取最大偶数长度回文
            evenMaxLength = evenPalindromeMaxLength(array, positionIndex);
        }
        return Math.max(oddMaxLength, evenMaxLength);
    }

    /**
     * 计算指定坐标奇数长度最大回文长度
     * @param array
     * @param positionIndex
     * @return
     */
    public static int oddPalindromeMaxLength(char[] array, int positionIndex) {
        // 最大回文长度
        int maxLength = 1;
        // 上一个元素
        int startIndex = positionIndex - 1;
        // 下一个元素
        int endIndex = positionIndex + 1;
        while (startIndex >= 0 && endIndex < array.length) {
            if (array[startIndex] == array[endIndex]) maxLength += 2;
            else return maxLength;
            startIndex--;
            endIndex++;
        }
        return maxLength;
    }

    /**
     * 计算指定坐标偶数长度最大回文长度
     * @param array
     * @param positionIndex
     * @return
     */
    public static int evenPalindromeMaxLength(char[] array, int positionIndex) {
        // 最大回文长度
        int maxLength = 2;
        // 上一个元素
        int startIndex = positionIndex - 1;
        // 下一个元素
        int endIndex = positionIndex + 1 + 1;
        while (startIndex >= 0 && endIndex < array.length) {
            if (array[startIndex] == array[endIndex]) maxLength += 2;
            else return maxLength;
            startIndex--;
            endIndex++;
        }
        return maxLength;
    }
}